Project Selection Problem

N個のプロジェクトがある

M個の機械がある

プロジェクトをやるためにはそのプロジェクトに必要な機械を買わなければならない

利益=収入-コストを最大化するにはどのプロジェクトを選べば良いか？

https://gyazo.com/052e99dda764a20363b0fea423f5cf79

頂点の塗り分けと解釈すると理解しやすい

スタートと同じ色で塗られたプロジェクトが「選択したプロジェクト」

同じ色で塗られたマシンが「購入されたマシン」

https://gyazo.com/9903f6866f0e9937fc6ee794b5f23090

図中の-pはrと読み替える

https://gyazo.com/a18e0dc6651304be872867f61f41f49d

----

N個のプロジェクトがある

M個の機械がある

プロジェクトはいくつかの機械を必要とする

プロジェクトpiを選ぶと収入r(pi)が得られる

必要な機械qjを買うとコストc(qj)が掛かる

利益-コストを最大化するにはどのプロジェクトを選べば良いか？

https://gyazo.com/22cdb18d63c33e3a302b1e21192343e7

「あるプロジェクトが選ばれたなら、必要な機械を買わなければならない」と言う制約を無限大の辺で表現する

右側か左側かどちらかを切らなければならない

プロジェクトの辺を切らないことを「プロジェクトの選択」と見る

機械の辺を切ることを「機械の購入」と見る

プロジェクトを選択した(辺を切らない)なら、機械を購入する(辺を切る)必要がある

プロジェクトを選択しない=収入減、機械を買う=コスト、この和を最小化したい→最小カット

https://gyazo.com/978ffe04cab172fb6ea7a364eb743e4b

二択の選択肢から選ぶ問題とも解釈できる